<template>
  <ExamPaper
    :items="paper"
    :name="title"
    @update:answers="val => (finalAnswers = val)"
  />
</template>

<script setup>
import { ref, onMounted, computed } from 'vue'
import ExamPaper from '@/components/ExamPaper.vue'
import { useRoute } from 'vue-router'
const route = useRoute()
const title =  computed(() => {
  return route.meta.title  || '算法题库'
})
const paper = ref([
  {
    question: `
    344. 反转字符串
    编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

    不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

    

    示例 1：

    输入：s = ["h","e","l","l","o"]
    输出：["o","l","l","e","h"]
    示例 2：

    输入：s = ["H","a","n","n","a","h"]
    输出：["h","a","n","n","a","H"]
    

    提示：

    1 <= s.length <= 105
    s[i] 都是 ASCII 码表中的可打印字符
    `,
    answer: 
    `
    // 方法一
    var reverseString = function(s) {
        return s.reverse()
    };
    // 方法二
    var reverseString = function(s) {
        const length = s.length;
        for(let i=0;i<length;i++){
            s.splice(i,0,s.splice(length-1,1)[0])
        }
        return s
    };
    `
  },
  {
    question: 
    `
    542. 01 矩阵
    中等
    相关标签
    premium lock icon
    相关企业
    给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。

    两个相邻元素间的距离为 1 。

    

    示例 1：
    <img alt="" src="https://pic.leetcode-cn.com/1626667201-NCWmuP-image.png" style="width: 150px;">


    输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
    输出：[[0,0,0],[0,1,0],[0,0,0]]
    示例 2：
    <img alt="" src="https://pic.leetcode-cn.com/1626667205-xFxIeK-image.png" style="width: 150px;">


    输入：mat = [[0,0,0],[0,1,0],[1,1,1]]
    输出：[[0,0,0],[0,1,0],[1,2,1]]
    

    提示：

    m == mat.length
    n == mat[i].length
    1 <= m, n <= 104
    1 <= m * n <= 104
    mat[i][j] is either 0 or 1.
    mat 中至少有一个 0 
    `,
    answer:
    `
    /**「多源 BFS」广度优先搜索
     * 计算 01 矩阵中每个元素到最近的 0 的距离
     * @param {number[][]} matrix 原始 01 矩阵
     * @return {number[][]} 距离矩阵（原地修改后返回）
     */
    const updateMatrix = function (matrix) {
        const rowCount = matrix.length;
        const colCount = matrix[0].length;
        const queue = [];

        // 1. 初始扫描：把所有 0 加入队列；把 1 标记为“待计算”状态 (-1)
        for (let row = 0; row < rowCount; row++) {
            for (let col = 0; col < colCount; col++) {
            if (matrix[row][col] === 0) {
                queue.push([row, col]); // 多源 BFS 的起点
            } else {
                matrix[row][col] = -1; // -1 表示“尚未算出距离”
            }
            }
        }

        // 四个相邻方向：下、上、右、左
        const directions = [
            [1, 0], // down
            [-1, 0], // up
            [0, 1], // right
            [0, -1] // left
        ];

        // 2. 一层层向外扩展，首次访问即为最近距离
        while (queue.length) {
            const [currentRow, currentCol] = queue.shift();
            const currentDistance = matrix[currentRow][currentCol];

            for (const [deltaRow, deltaCol] of directions) {
                const neighborRow = currentRow + deltaRow;
                const neighborCol = currentCol + deltaCol;

                // 越界或已计算过则跳过
                if (
                    neighborRow < 0 ||
                    neighborRow >= rowCount ||
                    neighborCol < 0 ||
                    neighborCol >= colCount ||
                    matrix[neighborRow][neighborCol] !== -1
                ) {
                    continue;
                }

                // 更新邻居距离并入队，等待后续扩展
                matrix[neighborRow][neighborCol] = currentDistance + 1;
                queue.push([neighborRow, neighborCol]);
            }
        }

        return matrix;
    };

    /* 示例用法
    const mat = [
    [0, 0, 0],
    [0, 1, 0],
    [1, 1, 1]
    ];
    console.log(updateMatrix(mat));
    // 输出：
    // [
    //   [0, 0, 0],
    //   [0, 1, 0],
    //   [1, 2, 1]
    // ]
    */
    `
  },
  {
    question: 
    `
    给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

    岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

    此外，你可以假设该网格的四条边均被水包围。

    

    示例 1：

    输入：grid = [
      ['1','1','1','1','0'],
      ['1','1','0','1','0'],
      ['1','1','0','0','0'],
      ['0','0','0','0','0']
    ]
    输出：1
    示例 2：

    输入：grid = [
      ['1','1','0','0','0'],
      ['1','1','0','0','0'],
      ['0','0','1','0','0'],
      ['0','0','0','1','1']
    ]
    输出：3
    `,
    answer:
    `
    function numIslands(grid) {
      let count = 0;
      const visited = new Set();
      const dfs = (row, col) => {
          if (
              row < 0 ||
              row >= grid.length ||
              col < 0 ||
              col >= grid[0].length ||
              grid[row][col] === '0' ||
              visited.has(\`\${row}-\${col}\`)
          ) {
              return;
          }
          visited.add(\`\${row}-\${col}\`);
          dfs(row + 1, col);
          dfs(row - 1, col);
          dfs(row, col + 1);
          dfs(row, col - 1);
      }
      for (let i = 0; i < grid.length; i++) {
          for (let j = 0; j < grid[0].length; j++) {
              if (grid[i][j] === '1' && !visited.has(\`\${i}-\${j}\`)) {
                  dfs(i, j);
                  count++;
              }
          }
      }
      return count;
  }
    `
  },
])
function numIslands(grid) {
    let count = 0;
    const visited = new Set();
    const dfs = (row, col) => {
        if (
            row < 0 ||
            row >= grid.length ||
            col < 0 ||
            col >= grid[0].length ||
            grid[row][col] === '0' ||
            visited.has(`${row}-${col}`)
        ) {
            return;
        }
        visited.add(`${row}-${col}`);
        dfs(row + 1, col);
        dfs(row - 1, col);
        dfs(row, col + 1);
        dfs(row, col - 1);
    }
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            if (grid[i][j] === '1' && !visited.has(`${i}-${j}`)) {
                dfs(i, j);
                count++;
            }
        }
    }
    return count;
}
onMounted(()=>{
    const grid =  [
      ['1','1','0','0','0'],
      ['1','1','0','0','0'],
      ['0','0','1','0','0'],
      ['0','0','0','1','1']
    ]
    console.log(numIslands(grid));
})


const finalAnswers = ref([])   // 实时收集到的答案
</script>